package com.sx.sx1.lintcode.day717;

public class LC207 {

    static class Solution {
        SegmentNode root = null;

        public Solution(int[] A) {
            if(A ==null || A.length ==0) return;
            root = buildXDTree(A, 0, A.length - 1);
        }


        public long query(int start, int end) {
            return query(root,start,end);
        }

        public long query(SegmentNode node,int start,int end){
            if(start<= node.start && end >= node.end) return node.val;
            int m =node.start+(node.end-node.start)/2;
            long left =0;
            long right =0;

            if(m>=start){
                left = query(node.left,start,Math.min(m,end));
            }

            if(m<end){
                right = query(node.right,m>=start?m+1:start,end);
            }
            return left+right;
        }


        public void modify(int index, int value) { //修改index处的值
            modify(root, index, value);
        }

        public void modify(SegmentNode node, int index, int value) {
            if (node.start == node.end && node.start == index) {
                node.val = value;
                return;
            }

            int m = node.start + (node.end - node.start) / 2;
            if (index <= m) {
                modify(node.left, index, value);
            } else {
                modify(node.right, index, value);
            }

            node.val = node.left.val+node.right.val;
        }

        public SegmentNode buildXDTree(int[] arr, int start, int end) {
            if (start == end) {
                return new SegmentNode(start, end, arr[start]);
            }
            SegmentNode root = new SegmentNode(start, end, 0);
            int m = start + (end - start) / 2;
            root.left = buildXDTree(arr, start, m);
            root.right = buildXDTree(arr, m + 1, end);

            root.val = root.left.val + root.right.val;

            return root;
        }

        static class SegmentNode {
            public int start, end;
            public long val;
            public SegmentNode left, right;

            public SegmentNode(int s, int e, int v) {
                start = s;
                end = e;
                val = v;
            }
        }
    }


    public static void main(String[] args) {
        Solution obj1 = new Solution(new int[]{});
        Solution obj = new Solution(new int[]{1,2,7,8,5});

        System.out.println(obj.query(0,2));
        obj.modify(0,4);
        System.out.println(obj.query(0,1));
        obj.modify(2,1);
        System.out.println(obj.query(2,4));

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有185条未读消息，请及时查看
207 · 区间求和 II
算法
困难
通过率
36%

题目
题解17
笔记
讨论99+
排名
记录
描述
在类的构造函数中给一个整数数组, 实现两个方法 query(start, end) 和 modify(index, value):

对于 query(start, end), 返回数组中下标 start 到 end 的 和。
对于 modify(index, value),把数组中下标为 index 的数改为 value.
最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


在做此题前，建议先完成以下三题：线段树的构造， 线段树的查询，以及线段树的修改。

样例
样例1

输入:
[1,2,7,8,5]
[query(0,2),modify(0,4),query(0,1),modify(2,1),query(2,4)]
输出: [10,6,14]
说明:
给定数组 A = [1,2,7,8,5].
在query(0, 2)后, 1 + 2 + 7 = 10,
在modify(0, 4)后, 将 A[0] 修改为 4， A = [4,2,7,8,5].
在query(0, 1)后, 4 + 2 = 6.
在modify(2, 1)后, 将 A[2] 修改为 1，A = [4,2,1,8,5].
After query(2, 4), 1 + 8 + 5 = 14.
样例2

输入:
[1,2,3,4,5]
[query(0,0),query(1,2),quert(3,4)]
输出: [1,5,9]
说明:
1 = 1
2 + 3 = 5
4 + 5 = 9
挑战
query 和 modify的时间复杂度需要为O(logN).

相关知识
学习《算法求职课——百题精讲》课程中的13.5区间求和 II-视频讲解相关内容 ，了解更多相关知识！
标签
相关题目

205
区间最小数
中等

206
区间求和 I
中等
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
45 分 00 秒
12345678910111213141516171819202122232425262728
public class Solution {
    /* you may need to use some attributes here


    public Solution(int[] A) {
        // do intialization if necessary
    }

…     * @param index: An integer
        * @param value: An integer
        * @return: nothing

public void modify(int index, int value) {
        // write your code here
        }
        }
        控制台
        历史提交



 373 ms
时间消耗
·
18.59 MB
空间消耗
·
输入数据
[]
[]
期望答案
[]
异常信息
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
	at Solution.buildXDTree(Solution.java:52)
	at Solution.buildXDTree(Solution.java:56)

 */
